//
// Created by Administrator on 2021/4/14.
//

/*
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。

例如，

给定二叉搜索树:

4
/ \
      2   7
/ \
    1   3

和值: 2
你应该返回如下子树:

2
/ \
    1   3
在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-in-a-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;


struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

    virtual ~TreeNode() {
        val = 0;
        left = nullptr;
        right = nullptr;
    }
};

void preorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) {
        return;
    }
    res.push_back(root->val);
    preorder(root->left, res); // 对左子节点递归调用
    preorder(root->right, res); // 对右子节点递归调用
}

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> res; // 结果向量
    preorder(root, res);
    return res;
}

class Solution {
public:
    TreeNode *searchBST(TreeNode *root, int val) {
        if (!root or root->val == val) return root;
        return val > root->val ? searchBST(root->right, val) : searchBST(root->left, val);
    }
};

class Solution2 {
public:
    TreeNode *searchBST(TreeNode *root, int val) {
        while (root != nullptr && val != root->val)
            root = val < root->val ? root->left : root->right;
        return root;
    }
};


int main() {
    auto t5 = TreeNode(3);
    auto t4 = TreeNode(1);
    auto t3 = TreeNode(7);
    auto t2 = TreeNode(2, &t4, &t5);
    auto t1 = TreeNode(4, &t2, &t3);
    Solution2 sol;
    auto ans = sol.searchBST(&t1, 2);
    cout << (ans ? ans->val : -1) << endl;
    if (ans) {
        vector<int> v = preorderTraversal(ans);
        for (auto &x:v) cout << x << endl;
    }
    return 0;
}
